import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution02 {
	public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		PriorityQueue<Integer[]> maxHeap = new PriorityQueue<>(
				(e1, e2) -> e2[0] + e2[1] - e1[0] - e1[1]);

		// 插入数据
		for (int i = 0; i < Math.min(k, nums1.length); i++) {
			for (int j = 0; j < Math.min(nums2.length, k); j++) {
				if (maxHeap.size() >= k) {
					Integer[] root = maxHeap.peek();
					if (root[0] + root[1] > nums1[i] + nums2[j]) {
						maxHeap.poll();
						maxHeap.offer(new Integer[] { nums1[i], nums2[j] });
					}
				} else {
					maxHeap.offer(new Integer[] { nums1[i], nums2[j] });
				}

			}
		}

		// 取出数据
		List<List<Integer>> result = new LinkedList<>();
		while (!maxHeap.isEmpty()) {
			Integer[] tmp = maxHeap.poll();
			result.add(Arrays.asList(tmp[0], tmp[1]));
		}
		return result;
	}
}
